//
// Created by yanhai on 2021/1/3.
//

// 归并排序 - 递归版本
// 思想：分而治之，先把一个整体，无限制的分成最小，
//      然后再把这些小的组一点点有序的归并起来，最后归并成一个完整的有序的集合
// 先递归细分(自上而下) -> 再排序归并(自下而上)

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

// 核心代码：将start到middle和middle+1到end的两个有序集合合并为一个start到end的有序集合
void _sort(int *data, int *temp, int start, int middle, int end)
{
    int i = start, j = middle + 1, k = start;
    while (i <= middle && j <= end) {
        // 这里应该加上等号
        // 假如data[i]==data[j]，如果不加等号，那么就会把data[j]放到前面，造成排序是不稳定的
        if (data[i] <= data[j]) {
            temp[k++] = data[i++];
        } else {
            temp[k++] = data[j++];
        }
    }
    // 将剩下的追加到temp后面
    while (i <= middle) {
        temp[k++] = data[i++];
    }
    while (j <= end) {
        temp[k++] = data[j++];
    }
    // 再把临时数据拷贝到data中
    for (i = start; i <= end; i++) {
        data[i] = temp[i];
    }
}

// 只要是start<end就继续拆分，start<end表示每个组还有多个元素
// 当每个组就只有1个元素时，就开始返回，开始执行_sort进行两两归并
void _merge_sort(int *data, int *temp, int start, int end)
{
    if (start < end) {
        int middle = start + (end - start) / 2;     // 分成2部分
        _merge_sort(data, temp, start, middle);     // 将前面的部分进行排序
        _merge_sort(data, temp, middle + 1, end);   // 将后面的部分进行排序
        _sort(data, temp, start, middle, end);      // 将两个有序的和并成为一个有序的
    }
}

// 申请临时空间，递归函数_merge_sort的入口
// 由于只申请了一块和元数据长度一样的内存空间，因此空间复杂度是O(n)
// 时间复杂度为 O(nlogn)
int merge_sort(int *data, int length)
{
    // 准备临时空间
    int *temp = (int *) malloc(length * sizeof(int));
    if (temp == NULL) {
        return 1;
    }
    _merge_sort(data, temp, 0, length - 1);
    free(temp);
    return 0;
}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {71, 64, 24, 12, 9, 16, 53, 57, 23, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    merge_sort(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
